package com.dzu.medium;

/**
 * @author ZhaoDong
 * @date 2022/11/2 9:46
 * @description 686. 重复叠加字符串匹配
 */
public class Test686 {
    public static void main(String[] args) {
        System.out.println(repeatedStringMatch2("a", "aa"));
    }


    /**
     * kmp
     *
     * @param a
     * @param b
     * @return
     */
    public static int repeatedStringMatch2(String a, String b) {

        StringBuilder sb = new StringBuilder();
        int ans = 0;
        while (sb.length() < b.length() && ++ans > 0) {
            sb.append(a);
        }
        sb.append(a);
        int idx = strStr(sb.toString(), b);
        if (idx == -1) {
            return -1;
        }
        return idx + b.length() > a.length() * ans ? ans + 1 : ans;
    }

    static int strStr(String ss, String pp) {
        if (pp.isEmpty()) {
            return 0;
        }
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        int[] next = new int[p.length + 1];
        for (int i = 1, j = 0; i < p.length; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = next[j - 1];
            }
            if (p[i] == p[j]) {
                j++;
            }
            next[i] = j;
        }
        for (int i = 0, j = 0; i < s.length; i++) {

            while (j > 0 && s[i] != p[j]) {
                j = next[j - 1];
            }

            if (s[i] == p[j]) {
                j++;
            }
            if (j == p.length) {
                return i - p.length + 1;
            }

        }
        return -1;
    }

    public static int repeatedStringMatch(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int ans = 0;
        while (sb.length() < b.length() && ++ans > 0) {
            sb.append(a);
        }
        sb.append(a);
        int idx = sb.indexOf(b);
        if (idx == -1) {
            return -1;
        }
        return idx + b.length() > a.length() * ans ? ans + 1 : ans;

//        StringBuffer sb = new StringBuffer();
//        int ans = 0;
//        int max = 2 * a.length() + b.length();
//        while (sb.length() < max) {
//            sb.append(a);
//            ans++;
//            if (sb.toString().contains(b)) {
//                return ans;
//            }
//        }
//        return -1;
    }
}
